package binaryTree;

import com.sun.source.tree.BinaryTree;
import com.sun.source.tree.Tree;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description: 二叉树练习
 * User: 王圆豪
 * Date: 2024-08-21
 * Time: 17:41
 */
 class TreeNode {
     char val;
     TreeNode left;
     TreeNode right;
     TreeNode() {}
     TreeNode(char val) { this.val = val; }
     TreeNode(char val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
 }

public class Solution {
    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode('A');
        treeNode1.left = new TreeNode('B');
        treeNode1.right = new TreeNode('C');
        TreeNode treeNode2 = new TreeNode('A');
        treeNode2.left = new TreeNode('B');
        treeNode2.right = new TreeNode('C');
        
//        TreeNode l = invertTree(treeNode1);
//        display(l);

//        System.out.println(isSameTree1(treeNode1, treeNode2));

//        System.out.println(isSymmetric1(treeNode1));

//        System.out.println(isSubtree(treeNode1, treeNode2));

//        System.out.println(isBalanced1(treeNode1));

//        System.out.println(isSubtree(treeNode1, treeNode2));

        for (int k:
             preorderTraversal1(treeNode1)) {
            System.out.print(k + " ");
        }
    }

    public static void display(TreeNode treeNode) {
        if (treeNode == null) return;
        System.out.print(treeNode.val + " ");
        display(treeNode.left);
        display(treeNode.right);
    }

    //后序遍历迭代
    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        TreeNode cur = null;

        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }

            root = stack.pop();
            if(root.right == null || root.right == cur){
                list.add((int)root.val);
                cur = root;
                root = null;
            }else{
                stack.push(root);
                root = root.right;
            }
        }
        return list;
    }

    //前序排列迭代
    public static List<Integer> preorderTraversal1(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while(cur != null || !stack.isEmpty()) {
            while(cur != null){
                stack.push(cur);
                list.add((int)cur.val);
                cur = cur.left;
            }

            cur = stack.pop();

            cur = cur.right;
        }
        return list;
    }
    //中序遍历迭代法
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }

            cur = stack.pop();
            list.add((int)cur.val);

            cur = cur.right;
        }
        return list;
    }
    //平衡二叉树
    public static boolean isBalanced1(TreeNode root) {
        if (root == null) return true;
        if (Math.abs(high(root.left) - high(root.right)) >= 2) {
            return false;
        }
        return isBalanced1(root.right) && isBalanced1(root.left);
    }
    public static int high(TreeNode treeNode) {
        if (treeNode == null) return 0;
        int hl = high(treeNode.left) + 1;
        int hr = high(treeNode.right) + 1;
        return Math.max(hl, hr);
    }
    //对称二叉树
    public static boolean isSymmetric1(TreeNode root) {
        if (root == null) return true;
        return isSameTree1(root.left, root.right);
    }
    //判断是相同树
    public static boolean isSameTree1(TreeNode p, TreeNode q) {
        if (p != null && q != null) {
            if (p.val != q.val) return false;
            return isSameTree1(p.left, q.right) && isSameTree1(p.right, q.left);
        }
        return q == p;
    }
     //反转二叉树
    public static TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode cur = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(cur);
        return root;
    }
    //层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null){
            return new ArrayList<>();
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        List<List<Integer>> l = new ArrayList<>();
        while (!queue.isEmpty()) {
            List<Integer> ll = new ArrayList<>();
            int sz = queue.size();
            while (sz != 0) {
                TreeNode cur2 = queue.poll();
                if (cur2.left != null) {
                    queue.offer(cur2.left);
                }
                if (cur2.right != null) {
                    queue.offer(cur2.right);
                }
                ll.add((int) cur2.val);
                sz--;
            }
            l.add(ll);
        }
        return l;
    }
    public static void main1(String[] args) {
//        TreeNode treeNode1 = new TreeNode(1);
//        treeNode1.left = new TreeNode(3);
//        treeNode1.right = new TreeNode(3);
//        TreeNode treeNode2 = new TreeNode(1);
//        treeNode2.left = new TreeNode(2);
//        treeNode2.right = new TreeNode(3);

//        System.out.println(isSameTree(treeNode1, treeNode2));

//        System.out.println(isSubtree(treeNode1, treeNode2));

//        TreeNode l = invertTree(treeNode1);
//        System.out.println(l.val + " " + l.left.val + " " + l.right.val);

//        System.out.println(isSymmetric(null));

//        System.out.println(isBalanced(treeNode1));
    }

    //二叉树的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)  {
        if (root == null) return null;

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (right != null) return right;
        return root;
    }

//    public boolean isContain(TreeNode root, TreeNode p) {
//        if (root == null) return false;
//        if (root == p) {
//            return true;
//        }
//        return isContain(root.left, p) || isContain(root.right, p);
//    }
    //二叉树的构建及遍历
    public static void main2(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String s = sc.nextLine();
            inorder(createTree(s));
            System.out.println();
        }
    }

    public static int i = 0;
    public static TreeNode createTree(String s){
        TreeNode root = null;
        if (s.charAt(i) != '#') {
            root = new TreeNode(s.charAt(i));
            i++;
            root.left = createTree(s);
            root.right = createTree(s);
        }else {
            i++;
        }
        return root;
    }
    public static void inorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }
    //平衡二叉树
    public static boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (Math.abs(getHigh(root.left) - getHigh(root.right)) >= 2) {
            return false;
        }
        return isBalanced(root.right) && isBalanced(root.left);
    }

    public static int getHigh(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(getHigh(root.left), getHigh(root.right)) + 1;
    }

    //对称二叉树
    public static boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSameTree(root.left, root.right);
    }
    //翻转二叉树
    public static TreeNode invertTree1(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode tmp = root.left;
        root.left = invertTree1(root.right);
        root.right = invertTree1(tmp);
        return root;
    }
    //另一棵树的子树
    public static boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (isSameTree(root, subRoot) || subRoot == null) {
            return true;
        }
        return root != null && (isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot));
    }
    //判断两棵树是否相同
    public static boolean isSameTree(TreeNode p, TreeNode q) {
        if (p != null && q != null) {
            if (q.val != p.val) {
                return false;
            }
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
        return p == q;
    }

    //二叉树的前序遍历
     List<Integer> l = new LinkedList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) {
            return l;
        }
//        l.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return l;
    }
}
